package com.wtpaint.algorithm.sort;

import com.wtpaint.algorithm.SortUtil;

import java.util.Random;

public class QuickSort {
    private QuickSort() {
    }

    public static void sort(Comparable[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(Comparable[] arr, int start, int end) {
//        if (start >= end) {
//            return;
//        }
        //优化1：插入排序进行优化
        if (end - start <= 15) {
            insertionSort(arr, start, end);
            return;
        }
        int p = partition(arr, start, end);
        quickSort(arr, start, p - 1);
        quickSort(arr, p + 1, end);
    }

    private static int partition(Comparable[] arr, int start, int end) {
        //优化2：随机标准点
        swap(arr, start, new Random().nextInt(end - start + 1) + start);
        //1、找出一个标准
        Comparable v = arr[start];

        //比标准大的放在右边，比标准小的放在左边
        int j = start;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i].compareTo(v) < 0) {
                swap(arr, j + 1, i);
                j++;
            }
        }
        //将标准与中间值交换
        swap(arr, start, j);
        return j;
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


    public static void insertionSort(Comparable[] arr, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            Comparable temp = arr[i];
            int j;
            for (j = i; j > start && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }


    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = SortUtil.generateRandomArray(n, 10, 21);
        SortUtil.testSort("com.wtpaint.algorithm.sort.QuickSort", arr);
//        SortUtil.printArray(arr);
    }

}
